package com.formula.datastructure.question.graph;

import com.formula.datastructure.standard.graph.*;
import com.formula.datastructure.util.DataUtil;

/* 最小生成树问题, 由一个图得到权值最小生成树
   1. N个顶点, N-1条边
   2. 包含全部顶点
   3. N-1条边本身存在图中
 */
public class MinGenTree {
    public static void main(String[] args) {
        testAdjMatrix();
        //testAdjLists();
    }

    public static void testAdjLists() {
        ALVertex[] vertexes = new ALVertex[6];
        ALVertex vertex1 = new ALVertex("a");
        ALVertex vertex2 = new ALVertex("b");
        ALVertex vertex3 = new ALVertex("c");
        ALVertex vertex4 = new ALVertex("d");
        ALVertex vertex5 = new ALVertex("e");
        ALVertex vertex6 = new ALVertex("f");
        vertexes[0] = vertex1;
        vertex1.idx = 0;
        vertexes[1] = vertex2;
        vertex2.idx = 1;
        vertexes[2] = vertex3;
        vertex3.idx = 2;
        vertexes[3] = vertex4;
        vertex4.idx = 3;
        vertexes[4] = vertex5;
        vertex5.idx = 4;
        vertexes[5] = vertex6;
        vertex6.idx = 5;

        ALEdge edge1 = new ALEdge(1, 7);
        ALEdge edge2 = new ALEdge(2, 5);
        vertex1.addEdge(edge1);
        vertex1.addEdge(edge2);

        ALEdge edge3 = new ALEdge(4, 3);
        ALEdge edge4 = new ALEdge(5, 4);
        vertex2.addEdge(edge3);
        vertex2.addEdge(edge4);
        ALEdge edge5 = new ALEdge(1, 2);
        ALEdge edge6 = new ALEdge(3, 3);
        vertex3.addEdge(edge5);
        vertex3.addEdge(edge6);
        ALEdge edge7 = new ALEdge(5, 5);
        vertex5.addEdge(edge7);
        ALEdge edge8 = new ALEdge(2, 6);
        ALEdge edge9 = new ALEdge(3, 5);
        vertex6.addEdge(edge8);
        vertex6.addEdge(edge9);
        AdjListsGraph graph = new AdjListsGraph(vertexes);
        primAdjLists(graph);
        System.out.println("========================================");
        krskAdjLists(graph);
    }

    public static void testAdjMatrix() {
        String[] data = DataUtil.genStrArr(6);
        DataUtil.printStrArr(data);
        AdjMatrixGraph graph = new AdjMatrixGraph(data);
        graph.edges[0][1] = 6;
        graph.edges[1][0] = 6;

        graph.edges[0][2] = 5;
        graph.edges[2][0] = 5;

        graph.edges[1][2] = 4;
        graph.edges[2][1] = 4;

        graph.edges[1][3] = 2;
        graph.edges[3][1] = 2;

        graph.edges[1][5] = 4;
        graph.edges[5][1] = 4;

        graph.edges[4][5] = 1;
        graph.edges[5][4] = 1;

        graph.edges[3][4] = 4;
        graph.edges[4][3] = 4;

        graph.edges[2][4] = 7;
        graph.edges[4][2] = 7;
        primAdjMatrix(graph);
    }

    public static void primAdjMatrix(AdjMatrixGraph graph) {
        Prim prim = new Prim();
        prim.getMST(graph);
    }

    public static void primAdjLists(AdjListsGraph graph) {
        Prim prim = new Prim();
        prim.getMST(graph);
    }

    private static void krskAdjLists(AdjListsGraph graph) {
        Kruskal kruskal = new Kruskal();
        kruskal.getMST(graph);
    }
}
